package org.kk.array;

/**
 * 从二维数组中查找值
 * @author kk
 * @Date 2021/1/21
 */
public class FindNumber {
    public static void main(String[] args) {
        int[][] nums = new int[][]{
                {1,2,5,6,9},
                {2,4,7,10,14},
                {4,7,9,12,13},
                {3,5,6,10,16}
        };
        boolean b = find(nums, 6);
        System.out.println(b);
        b = find1(nums, 16);
        System.out.println(b);
    }
    /**
     * 第一种解法: 双指针 (推荐)
     * 时间复杂度：O(mn)，空间复杂度：O(1)
     */
    public static boolean find(int[][] arr, int target){
        if(arr == null || arr .length == 0 || arr[0].length == 0) return false;
        int rows = arr.length, columns = arr[0].length;
        int row = 0, column = columns -1;
        while(row < rows && column >= 0){
            int num = arr[row][column];
            if(num > target) {
                column--;
            }else if(num < target){
                row++;
            }else{
                return true;
            }
        }
        return false;
    }

    /**
     * 第二种解法: 二分法 (推荐)
     * 时间复杂度: O(log mn) 复杂度 O(1)
     */
    public static boolean find1(int[][] arr, int target){
        if(arr == null || arr.length == 0 || arr[0].length == 0) return false;
        int left = 0, right = arr.length * arr[0].length - 1;
        int column = arr[0].length;
        while(left <= right){
            int mid = (left + right) >>> 1;
            int num = arr[mid / column][mid % column];
            if(num < target){
                left = mid + 1;
            }else if(num > target){
                right = mid -1;
            }else {
                return true;
            }
        }
        return false;
    }
}
